import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution {
    public int[][] merge(int[][] intervals) {
        // 边界处理
        if (intervals == null || intervals.length <= 1) {
            return intervals;
        }

        // 按区间起始位置升序排序
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);

        List<int[]> merged = new ArrayList<>();
        // 先加入第一个区间作为初始合并对象
        merged.add(intervals[0]);

        // 遍历剩余区间，逐一合并
        for (int i = 1; i < intervals.length; i++) {
            int[] last = merged.get(merged.size() - 1); // 已合并区间的最后一个
            int[] curr = intervals[i]; // 现在待合并区间

            // 判断是否重叠：当前区间的起始 <= 最后一个合并区间的结束
            if (curr[0] <= last[1]) {
                last[1] = Math.max(last[1], curr[1]);
            } else {
                // 不重叠，直接加入结果
                merged.add(curr);
            }
        }

        return merged.toArray(new int[merged.size()][]);
    }
}